class Solution
{
public:
    int minimumAddedCoins(vector<int> &coins, int target)
    {
        sort(coins.begin(), coins.end());
        int result = 0;
        int n = coins.size();
        int curCoinId = 0;
        int maxReached = 0;
        int curTarget = 1;
        while (curTarget <= target)
        {
            if (curTarget <= maxReached)
            {
                ++curTarget;
                continue;
            }
            if (curCoinId < n && coins[curCoinId] <= curTarget)
            {
                maxReached += coins[curCoinId];
                ++curCoinId;
            }
            else
            {
                ++result;
                maxReached += curTarget;
            }
        }
        return result;
    }
};